class Solution(object):
    def maxDistance(self, position, m):
        position.sort()
        n = len(position)
        if m == 2:
            return position[-1] - position[0]
        else:
            def find(val):
                min_val = float('inf')
                now_count = 2
                last = 0
                index = 1
                while index < n - 1:
                    if position[index] - position[last] >= val:
                        min_val = min(min_val, position[index] - position[last])
                        now_count += 1
                        last = index
                        if now_count == m:
                            break
                    index += 1
                if now_count == m:
                    min_val = min(min_val, position[-1] - position[index])
                    if min_val >= val:
                        return min_val
                    else:
                        return -1
                else:
                    return -1

            left = 1
            right = position[-1] - position[0]
            while left < right:
                mid = (left + right + 1) // 2
                val = find(mid)
                if val == -1:
                    right = mid - 1
                else:
                    left = val
            return left